{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Node to Path in Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #树中最接近路径的节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>n</code>，表示树中的节点数，编号从 <code>0</code> 到 <code>n - 1</code> (<strong>含边界</strong>)。还给定一个长度为 <code>n - 1</code> 的二维整数数组 <code>edges</code>，其中&nbsp;<code>edges[i] = [node1<sub>i</sub>, node2<sub>i</sub>]</code> 表示有一条&nbsp;<strong>双向&nbsp;</strong>边连接树中的 <code>node1<sub>i</sub></code> 和 <code>node2<sub>i</sub></code>。</p>\n",
    "\n",
    "<p>给定一个长度为 <code>m</code>&nbsp;，<strong>下标从 0 开始</strong>&nbsp;的整数数组 <code>query</code>，其中 <code>query[i] = [start<sub>i</sub>, end<sub>i</sub>, node<sub>i</sub>]</code>&nbsp;意味着对于第 <code>i</code> 个查询，您的任务是从 <code>start<sub>i</sub></code> 到 <code>end<sub>i</sub></code> 的路径上找到&nbsp;<strong>最接近</strong> <code>node<sub>i</sub></code><sub>&nbsp;</sub>的节点。</p>\n",
    "\n",
    "<p>返回<em>长度为 <code>m</code> 的整数数组 </em><code>answer</code><em>，其中 </em><code>answer[i]</code>&nbsp;<em>是第 <code>i</code> 个查询的答案。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/14/image-20220514132158-1.png\" style=\"width: 300px; height: 211px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 7, edges = [[0,1],[0,2],[0,3],[1,4],[2,5],[2,6]], query = [[5,3,4],[5,3,6]]\n",
    "<strong>输出:</strong> [0,2]\n",
    "<strong>解释:</strong>\n",
    "节点 5 到节点 3 的路径由节点 5、2、0、3 组成。\n",
    "节点 4 到节点 0 的距离为 2。\n",
    "节点 0 是距离节点 4 最近的路径上的节点，因此第一个查询的答案是 0。\n",
    "节点 6 到节点 2 的距离为 1。\n",
    "节点 2 是距离节点 6 最近的路径上的节点，因此第二个查询的答案是 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/14/image-20220514132318-2.png\" style=\"width: 300px; height: 89px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3, edges = [[0,1],[1,2]], query = [[0,1,2]]\n",
    "<strong>输出:</strong> [1]\n",
    "<strong>解释:</strong>\n",
    "从节点 0 到节点 1 的路径由节点 0,1 组成。\n",
    "节点 2 到节点 1 的距离为 1。\n",
    "节点 1 是距离节点 2 最近的路径上的节点，因此第一个查询的答案是 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/05/14/image-20220514132333-3.png\" style=\"width: 300px; height: 89px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3, edges = [[0,1],[1,2]], query = [[0,0,0]]\n",
    "<strong>输出:</strong> [0]\n",
    "<strong>解释:</strong>\n",
    "节点 0 到节点 0 的路径由节点 0 组成。\n",
    "因为 0 是路径上唯一的节点，所以第一个查询的答案是0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= node1<sub>i</sub>, node2<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>node1<sub>i</sub> != node2<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= query.length &lt;= 1000</code></li>\n",
    "\t<li><code>query[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub>, end<sub>i</sub>, node<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">这个图是一个树。</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-node-to-path-in-tree](https://leetcode.cn/problems/closest-node-to-path-in-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-node-to-path-in-tree](https://leetcode.cn/problems/closest-node-to-path-in-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,1],[0,2],[0,3],[1,4],[2,5],[2,6]]\\n[[5,3,4],[5,3,6]]', '3\\n[[0,1],[1,2]]\\n[[0,1,2]]', '3\\n[[0,1],[1,2]]\\n[[0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        m = len(query)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = []\n",
    "        def dfs(x, fa, target):\n",
    "            if target == x:\n",
    "                return [x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    ans = dfs(y, x, target)\n",
    "                    if ans:\n",
    "                        return [x] + ans\n",
    "            return []\n",
    "\n",
    "        def dfs2(x, fa, target):\n",
    "            if x in target:\n",
    "                return x\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    ans = dfs2(y, x, target)\n",
    "                    if ans != -1: return ans\n",
    "            return -1\n",
    "\n",
    "        for i in range(m):\n",
    "            s, e, node = query[i]\n",
    "            path = dfs(s, -1, e)\n",
    "            ans.append(dfs2(node, -1, path))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        m = len(query)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = []\n",
    "        def dfs(x, fa, target):\n",
    "            if target == x:\n",
    "                return [x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    ans = dfs(y, x, target)\n",
    "                    if ans:\n",
    "                        return [x] + ans\n",
    "            return []\n",
    "\n",
    "        def dfs2(x, fa, target):\n",
    "            if x in target:\n",
    "                return x\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    ans = dfs2(y, x, target)\n",
    "                    if ans != -1: return ans\n",
    "            return -1\n",
    "\n",
    "        for i in range(m):\n",
    "            s, e, node = query[i]\n",
    "            path = dfs(s, -1, e)\n",
    "            ans.append(dfs2(node, -1, path))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adjMap[u].add(v)\n",
    "            adjMap[v].add(u)\n",
    "        LCA = LCAManager(n, adjMap)\n",
    "\n",
    "        res = []  # 答案是最(靠下)深的LCA\n",
    "        for root1, root2, root3 in query:\n",
    "            res.append(\n",
    "                max(\n",
    "                    LCA.queryLCA(root1, root3),\n",
    "                    LCA.queryLCA(root2, root3),\n",
    "                    LCA.queryLCA(root1, root2),\n",
    "                    key=lambda lca: LCA.depth[lca],\n",
    "                )\n",
    "            )\n",
    "        return res\n",
    "\n",
    "\n",
    "class LCAManager:\n",
    "    def __init__(self, n: int, adjMap: DefaultDict[int, Set[int]]) -> None:\n",
    "        \"\"\"查询 LCA\n",
    "\n",
    "        `nlogn` 预处理\n",
    "        `logn`查询两点的LCA\n",
    "\n",
    "        Args:\n",
    "            n (int): 树节点编号 默认 0 ~ n-1 根节点为 0\n",
    "            adjMap (DefaultDict[int, Set[int]]): 树\n",
    "        \"\"\"\n",
    "        self.depth = defaultdict(lambda: -1)\n",
    "        self.parent = defaultdict(lambda: -1)\n",
    "        self._BITLEN = floor(log2(n)) + 1\n",
    "        self._MAX = n\n",
    "        self._adjMap = adjMap\n",
    "        self._dfs(0, -1, 0)\n",
    "        self._dp = self._initDp(self.parent)\n",
    "\n",
    "    def queryLCA(self, root1: int, root2: int) -> int:\n",
    "        \"\"\" `logn` 查询 \"\"\"\n",
    "        if self.depth[root1] < self.depth[root2]:\n",
    "            root1, root2 = root2, root1\n",
    "\n",
    "        for i in range(self._BITLEN - 1, -1, -1):\n",
    "            if self.depth[self._dp[root1][i]] >= self.depth[root2]:\n",
    "                root1 = self._dp[root1][i]\n",
    "\n",
    "        if root1 == root2:\n",
    "            return root1\n",
    "\n",
    "        for i in range(self._BITLEN - 1, -1, -1):\n",
    "            if self._dp[root1][i] != self._dp[root2][i]:\n",
    "                root1 = self._dp[root1][i]\n",
    "                root2 = self._dp[root2][i]\n",
    "\n",
    "        return self._dp[root1][0]\n",
    "\n",
    "    def _dfs(self, cur: int, pre: int, dep: int) -> None:\n",
    "        \"\"\"处理高度、父节点信息\"\"\"\n",
    "        self.depth[cur], self.parent[cur] = dep, pre\n",
    "        for next in self._adjMap[cur]:\n",
    "            if next == pre:\n",
    "                continue\n",
    "            self._dfs(next, cur, dep + 1)\n",
    "\n",
    "    def _initDp(self, parent: DefaultDict[int, int]) -> List[List[int]]:\n",
    "        \"\"\"nlogn预处理\"\"\"\n",
    "        dp = [[0] * self._BITLEN for _ in range(self._MAX)]\n",
    "        for i in range(self._MAX):\n",
    "            dp[i][0] = parent[i]\n",
    "        for j in range(self._BITLEN - 1):\n",
    "            for i in range(self._MAX):\n",
    "                if dp[i][j] == -1:\n",
    "                    dp[i][j + 1] = -1\n",
    "                else:\n",
    "                    dp[i][j + 1] = dp[dp[i][j]][j]\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.check = False  # 成员变量用于标记DFS搜索是否成功\n",
    "    \n",
    "    def dfs(self, i, j, s, vis, G):\n",
    "        \"\"\"\n",
    "        DFS 方法用于找出两个节点之间的路径\n",
    "        :param i: 起始节点\n",
    "        :param j: 结束节点\n",
    "        :param s: 记录路径的集合\n",
    "        :param vis: 记录节点是否访问过的列表\n",
    "        :param G: 图的邻接表\n",
    "        \"\"\"\n",
    "        if i == j:\n",
    "            self.check = True\n",
    "            s.add(i)\n",
    "            return\n",
    "        \n",
    "        for temp in G[i]:\n",
    "            if not vis[temp]:\n",
    "                vis[temp] = True\n",
    "                self.dfs(temp, j, s, vis, G)\n",
    "            \n",
    "            if self.check:\n",
    "                s.add(temp)\n",
    "                return\n",
    "\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        主函数，解决最接近节点的问题\n",
    "        :param n: 节点数量\n",
    "        :param edges: 边的列表\n",
    "        :param query: 查询列表\n",
    "        :return: 返回每次查询的结果列表\n",
    "        \"\"\"\n",
    "        G = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "\n",
    "        ans = []  # 存储结果的列表\n",
    "        for i, j, k in query:\n",
    "            s = set()  # 存储路径的集合\n",
    "            s.add(i)\n",
    "            self.check = False\n",
    "            vis = [False] * n\n",
    "            vis[i] = True\n",
    "            self.dfs(i, j, s, vis, G)  # 找出i到j的路径\n",
    "            \n",
    "            if k in s:  # 如果k在路径里，则k就是答案\n",
    "                ans.append(k)\n",
    "                continue\n",
    "\n",
    "            vis = [False] * n\n",
    "            queue = deque()\n",
    "            queue.append(k)\n",
    "            vis[k] = True\n",
    "            \n",
    "            while queue:  # BFS查找k到路径上的第一个节点\n",
    "                m = queue.popleft()\n",
    "                for temp in G[m]:\n",
    "                    if temp in s:\n",
    "                        ans.append(temp)\n",
    "                        break\n",
    "                    elif not vis[temp]:\n",
    "                        vis[temp] = True\n",
    "                        queue.append(temp)\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 输入样例和测试代码可以放在这里\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        depth = defaultdict(int)\n",
    "        parent = defaultdict(int)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(x, fa, d):\n",
    "            depth[x] = d\n",
    "            parent[x] = fa\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x, d+1)\n",
    "\n",
    "        def helper(x, y):\n",
    "            res = {x, y}\n",
    "            if depth[x] < depth[y]:\n",
    "                for i in range(depth[y] - depth[x]):\n",
    "                    y = parent[y]\n",
    "                    res.add(y)\n",
    "            else:\n",
    "                for i in range(depth[x] - depth[y]):\n",
    "                    x = parent[x]\n",
    "                    res.add(x)\n",
    "            while x != y:\n",
    "                x = parent[x]\n",
    "                y = parent[y]\n",
    "                res.add(x)\n",
    "                res.add(y)\n",
    "            return res\n",
    "        \n",
    "        def bfs(x, s):\n",
    "            q = [x]\n",
    "            vis = set(q)\n",
    "            while q:\n",
    "                nq = []\n",
    "                for x in q:\n",
    "                    if x in s:\n",
    "                        return x\n",
    "                    for y in g[x]:\n",
    "                        if y not in vis:\n",
    "                            vis.add(y)\n",
    "                            nq.append(y)\n",
    "                q = nq\n",
    "            return None\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        return [bfs(z, helper(x, y)) for x, y, z in query]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        depth = defaultdict(int)\n",
    "        parent = defaultdict(int)\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(x, fa, d):\n",
    "            depth[x] = d\n",
    "            parent[x] = fa\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x, d+1)\n",
    "        \n",
    "        def helper(x, y):\n",
    "            res = {x, y}\n",
    "            if depth[x] < depth[y]:\n",
    "                for i in range(depth[y] - depth[x]):\n",
    "                    y = parent[y]\n",
    "                    res.add(y)\n",
    "            else:\n",
    "                for i in range(depth[x] - depth[y]):\n",
    "                    x = parent[x]\n",
    "                    res.add(x)\n",
    "            while x != y:\n",
    "                x = parent[x]\n",
    "                y = parent[y]\n",
    "                res.add(x)\n",
    "                res.add(y)\n",
    "            return res\n",
    "        \n",
    "        def bfs(x, s):\n",
    "            q = [x]\n",
    "            vis = set(q)\n",
    "            while q:\n",
    "                nq = []\n",
    "                for x in q:\n",
    "                    if x in s:\n",
    "                        return x\n",
    "                    for y in g[x]:\n",
    "                        if y not in vis:\n",
    "                            vis.add(y)\n",
    "                            nq.append(y)\n",
    "                q = nq\n",
    "            return None\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        return [bfs(z, helper(x, y)) for x, y, z in query]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(set)\n",
    "        depth = defaultdict(int)\n",
    "        parent = defaultdict(lambda: -1)\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        def dfs(x, fa, d):\n",
    "            depth[x] = d\n",
    "            parent[x] = fa\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x, d+1)\n",
    "        \n",
    "        def helper(x, y):\n",
    "            res = {x, y}\n",
    "            if depth[x] < depth[y]:\n",
    "                for i in range(depth[y] - depth[x]):\n",
    "                    y = parent[y]\n",
    "                    res.add(y)\n",
    "            else:\n",
    "                for i in range(depth[x] - depth[y]):\n",
    "                    x = parent[x]\n",
    "                    res.add(x)\n",
    "            while x != y:\n",
    "                x = parent[x]\n",
    "                y = parent[y]\n",
    "                res.add(x)\n",
    "                res.add(y)\n",
    "            return res\n",
    "        \n",
    "        def bfs(x, s):\n",
    "            q = [x]\n",
    "            vis = set(q)\n",
    "            while q:\n",
    "                nq = []\n",
    "                for x in q:\n",
    "                    if x in s:\n",
    "                        return x\n",
    "                    for y in g[x]:\n",
    "                        if y not in vis:\n",
    "                            vis.add(y)\n",
    "                            nq.append(y)\n",
    "                q = nq\n",
    "            return None\n",
    "        \n",
    "        dfs(0, -1, 0)\n",
    "        return [bfs(z, helper(x, y)) for x, y, z in query]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        def dfs(cur: int, pre: int, dep: int) -> None:\n",
    "            \"\"\"处理高度、父节点信息\"\"\"\n",
    "            depth[cur], parent[cur] = dep, pre\n",
    "            for next in adjMap[cur]:\n",
    "                if next == pre:\n",
    "                    continue\n",
    "                dfs(next, cur, dep + 1)\n",
    "\n",
    "        def getPath(\n",
    "            root1: int, root2: int, level: DefaultDict[int, int], parent: DefaultDict[int, int]\n",
    "        ) -> Set[int]:\n",
    "            \"\"\"求两个结点间的路径，不断上跳到LCA并记录经过的结点\"\"\"\n",
    "            res = {root1, root2}\n",
    "            if level[root1] < level[root2]:\n",
    "                root1, root2 = root2, root1\n",
    "            diff = level[root1] - level[root2]\n",
    "            for _ in range(diff):\n",
    "                root1 = parent[root1]\n",
    "                res |= {root1}\n",
    "            while root1 != root2:\n",
    "                root1 = parent[root1]\n",
    "                root2 = parent[root2]\n",
    "                res |= {root1, root2}\n",
    "            return res\n",
    "\n",
    "        def bfs(start: int, hit: Set[int]) -> int:\n",
    "            \"\"\"求到目标路径的最近交点\"\"\"\n",
    "            visited, queue = set([start]), deque([start])\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                if cur in hit:\n",
    "                    return cur\n",
    "                for next in adjMap[cur]:\n",
    "                    if next not in visited:\n",
    "                        visited.add(next)\n",
    "                        queue.append(next)\n",
    "            raise Exception(\"impossible\")\n",
    "\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adjMap[u].add(v)\n",
    "            adjMap[v].add(u)\n",
    "\n",
    "        depth, parent = defaultdict(int), defaultdict(lambda: -1)\n",
    "        dfs(0, -1, 0)\n",
    "        return [bfs(root3, getPath(root1, root2, depth, parent)) for root1, root2, root3 in query]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b), g[b].append(a)\n",
    "\n",
    "        g2 = collections.defaultdict(set)\n",
    "        for q in query:\n",
    "            for a, b in itertools.combinations(q, 2):\n",
    "                g2[a].add(b)\n",
    "                g2[b].add(a)\n",
    "\n",
    "        root = list(range(n))\n",
    "        pa = [0] * n\n",
    "        lca_dict = collections.defaultdict(int)\n",
    "        vis = [0] * n\n",
    "\n",
    "        def find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = find(root[x])\n",
    "            return root[x]\n",
    "\n",
    "        def tarjan(u, p):\n",
    "            pa[u] = p\n",
    "            for v in g[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                tarjan(v, u)\n",
    "                root[v] = u\n",
    "            for v in g2[u]:\n",
    "                if v == u:\n",
    "                    lca_dict[u, v] = u\n",
    "                elif vis[v]:\n",
    "                    lca_dict[u, v] = lca_dict[v, u] = find(v)\n",
    "            vis[u] = 1\n",
    "\n",
    "        tarjan(0, -1)\n",
    "        res = []\n",
    "        for a, b, c in query:\n",
    "            if lca_dict[a, b] == lca_dict[a, c]:\n",
    "                res.append(lca_dict[b, c])\n",
    "            elif lca_dict[a, b] == lca_dict[b, c]:\n",
    "                res.append(lca_dict[a, c])\n",
    "            else:\n",
    "                res.append(lca_dict[a, b])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b), g[b].append(a)\n",
    "\n",
    "        g2 = collections.defaultdict(set)\n",
    "        for q in query:\n",
    "            for a, b in itertools.combinations(q, 2):\n",
    "                g2[a].add(b)\n",
    "                g2[b].add(a)\n",
    "\n",
    "        root = list(range(n))\n",
    "        pa = [0] * n\n",
    "        lca_dict = collections.defaultdict(int)\n",
    "        vis = [0] * n\n",
    "\n",
    "        def find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = find(root[x])\n",
    "            return root[x]\n",
    "\n",
    "        def tarjan(u, p):\n",
    "            pa[u] = p\n",
    "            for v in g[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                tarjan(v, u)\n",
    "                root[v] = u\n",
    "            for v in g2[u]:\n",
    "                if v == u:\n",
    "                    lca_dict[u, v] = u\n",
    "                elif vis[v]:\n",
    "                    lca_dict[u, v] = lca_dict[v, u] = find(v)\n",
    "            vis[u] = 1\n",
    "\n",
    "        tarjan(0, -1)\n",
    "        res = []\n",
    "        for a, b, c in query:\n",
    "            if lca_dict[a, b] == lca_dict[a, c]:\n",
    "                res.append(lca_dict[b, c])\n",
    "            elif lca_dict[a, b] == lca_dict[b, c]:\n",
    "                res.append(lca_dict[a, c])\n",
    "            else:\n",
    "                res.append(lca_dict[a, b])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        dist = [[math.inf] * n for _ in range(n)]\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b), g[b].append(a)\n",
    "\n",
    "        g2 = collections.defaultdict(set)\n",
    "        for q in query:\n",
    "            for a, b in itertools.combinations(q, 2):\n",
    "                g2[a].add(b)\n",
    "                g2[b].add(a)\n",
    "\n",
    "\n",
    "        root = list(range(n))\n",
    "        pa = [0] * n\n",
    "        lca_dict = collections.defaultdict(int)\n",
    "        vis = [0] * n\n",
    "\n",
    "        def find(x):\n",
    "            if x != root[x]:\n",
    "                root[x] = find(root[x])\n",
    "            return root[x]\n",
    "\n",
    "        def tarjan(u, p):\n",
    "            pa[u] = p\n",
    "            for v in g[u]:\n",
    "                if v == p:\n",
    "                    continue\n",
    "                tarjan(v, u)\n",
    "                root[v] = u\n",
    "            for v in g2[u]:\n",
    "                if v == u:\n",
    "                    lca_dict[u, v] = u\n",
    "                elif vis[v]:\n",
    "                    lca_dict[u, v] = lca_dict[v, u] = find(v)\n",
    "            vis[u] = 1\n",
    "\n",
    "        tarjan(0, -1)\n",
    "        res = []\n",
    "        for a, b, c in query:\n",
    "            if lca_dict[a, b] == lca_dict[a, c]:\n",
    "                res.append(lca_dict[b, c])\n",
    "            elif lca_dict[a, b] == lca_dict[b, c]:\n",
    "                res.append(lca_dict[a, c])\n",
    "            else:\n",
    "                res.append(lca_dict[a, b])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        D = [[math.inf]*n for _ in range(n)]\n",
    "        for a in range(n):\n",
    "            que,D[a][a] = [a],0\n",
    "            while que:\n",
    "                tmp = []\n",
    "                for q in que:\n",
    "                    for b in G[q]:\n",
    "                        if D[a][b]!=math.inf: continue\n",
    "                        D[a][b]=D[a][q]+1\n",
    "                        tmp.append(b)\n",
    "                que = tmp\n",
    "        return [min(range(n), key=lambda x: D[x][a]+D[x][b]+D[x][q]) for a,b,q in query]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        dist = [[math.inf] * n for _ in range(n)]\n",
    "        g = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "            dq = collections.deque([i])\n",
    "            while dq:\n",
    "                u = dq.popleft()\n",
    "                for v in g[u]:\n",
    "                    if dist[i][v] == math.inf:\n",
    "                        dist[i][v] = dist[i][u] + 1\n",
    "                        dq.append(v)\n",
    "        \n",
    "        return [min(range(n), key=lambda x: dist[x][a] + dist[x][b] + dist[x][c]) for a, b, c in query]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        A = [[inf]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            Q = [(0,i)]\n",
    "            A[i][i] = 0\n",
    "            for w,u in Q:\n",
    "                for v in g[u]:\n",
    "                    if w+1<A[i][v]:\n",
    "                        A[i][v] = w+1\n",
    "                        Q.append((w+1,v))\n",
    "        return [min(range(n),key=lambda i:A[s][i]+A[e][i]+A[x][i]) for  s,e,x in query]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
